/*
 * @Author: wwssaabb
 * @Date: 2021-12-13 11:40:35
 * @LastEditTime: 2021-12-13 17:50:52
 * @FilePath: \handwritten-code\algorithm\最长公共前缀.js
 */

/* 
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀， 返回空字符串 ""。

示例 1：
输入： strs = ["flower", "flow", "flight"]
输出： "fl"

示例 2：
输入： strs = ["dog", "racecar", "car"]
输出： ""
解释： 输入不存在公共前缀。

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/longest-common-prefix
*/

//横向扫描，时间复杂度O(mn),空间复杂度O(1)
var longestCommonPrefix = function (strs) {
  if (!strs.length) return ''
  let res = strs[0]
  for (let i = 1; i < strs.length; i++) {
    let j = 0
    for (; j < res.length; ++j) {
      if (res[j] != strs[i][j]) break
    }
    res = res.slice(0, j)
    if (res === '') return res
  }
  return res
};

var longestCommonPrefix = function (strs) {
  if (!strs.length) return ''
  let res = strs[0]
  for (let i = 1; i < strs.length; i++) {
    const str = strs[i]
    for (let j = 0; j < res.length; j++) {
      if (str[j] !== res[j]) {
        res = res.slice(0, j);
        break;
      }
    }
  }
  return res
};


console.log(longestCommonPrefix(["flower", "flow", "flight"]))